#include <sys/time.h>

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int binSearchGeneral(vector<int>& nums, int l, int r, int t) {

  while(l<=r) {
    int m = (l+r)/2;
    if(t == nums.at(m)) {
      return m;
    } else if(t>nums.at(m)) {
      l = m+1;
    } else {
      r = m-1;
    }
  }

  return -1;
}

void binSearch(vector<int>& nums, int left, int right, int key, int& res){
  if(left>right)
    return;

  int mid=0;
  mid = (left+right)/2;
  if(nums.at(mid)>nums.at(left)) {
    if(key<=nums.at(mid)&&key>=nums.at(left)) {
      res = binSearchGeneral(nums, left, mid, key);
    } else {
      binSearch(nums, mid, right, key, res);
    }

  } else if(nums.at(mid)==nums.at(left)) {
    if(nums.at(mid)==key)
      res = mid;
    else if(nums.at(right)==key)
      res = right;
    else
      res = -1;

  } else {
    if(key>=nums.at(mid)&&key<=nums.at(right)) {
      res = binSearchGeneral(nums, mid, right, key);
    } else {
      binSearch(nums, left, mid, key, res);
    }
  }

}

int search(vector<int>& nums, int target) {
  int ret = -1;
  binSearch(nums, 0, nums.size()-1, target, ret);
  return ret;
}


int main(int argc, char* argv[]) {

  struct  timeval    tv1, tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1, &tz);

  vector<int> v = {4,1,2};//,6,7,8,1,2,3};
for(auto target : v) {
  int ret = search(v, target);
  cout << ret << endl;
}
int time2 = gettimeofday(&tv2, &tz);
cout << "time consuming local machine:" << endl
<< tv2.tv_usec - tv1.tv_usec 
<< "us" << endl;


return 0;
}
